import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-21
 * Time: 8:46
 */
public class Solution {
//     贪心算法
//     直接求需要删除的会议数不好求, 转化为最多能参加多少个会议
//     总共的会议数 - 最多能参加的数目 = 最少需要去除的会议数
//     每次都选结束时间最早的会议
//     前后两个会议的时间会出现三种情况
//     不交叉, 交叉又分为 普通的交叉和包含
    public static int eraseOverlapIntervals(int[][] intervals) {
        // 根据结束时间从小到大排序
        Arrays.sort(intervals, (o1, o2) -> o1[1] - o2[1]);
        int num = intervals.length;
        int count = 1;
        // 记录一下第一个事件的结束时间
        int endTime = intervals[0][1];
        for (int i = 1; i < num; i++) {
            if(intervals[i][0] >= endTime){
                // 前后两个事件没有交叉
                count++;
                endTime = intervals[i][1];
            }else{
                // 前后两个事件交叉, count 不变
                if (intervals[i][1] < endTime){
                    // 后面的这个事件结束时间更早, 就更新结束时间
                    endTime = intervals[i][1];
                }
                // 否则就不用更新
            }
        }
        return num - count;
    }
}
